package com.mxw.算法之美.a13字符串;

/**
 * @author Administrator
 * @create 2024/8/5 11:32
 */
public class a03BM算法 {

    /**
     * 坏字符规则： 从模式串的末尾往前倒着匹配，发现某个字符没法匹配的时候，把主串中这个没有匹配的字符叫做坏字符。
     * 好后缀规则： 决定模式串应该如何移动。
     * <p>
     * 滑动位数：发生不匹配的时候，把坏字符对应的模式串中的字符下标为si。如果坏字符在模式串中存在，在模式串中的下标为xi，xi=下标值。 如果不存在，xi为-1。 模式移动的位数：si-xi
     */

    private static final int SIZE = 256;


    // bc 记录模式串的每个字符位置  b是模式串
    private void generateBc(char[] b, int[] bc) {
        int m = b.length;
        for (int i = 0; i < SIZE; i++) {
            bc[i] = -1;
        }
        for (int i = 0; i < m; i++) {
            int ascii = (int) b[i];
            bc[ascii] = i;
        }
    }

    private int bm(char[] a, int n, char[] b, int m) {
        // 记录模式串中每个字符最后出现的位置
        int[] bc = new int[SIZE];
        // 坏字符哈希表
        generateBc(b, bc);
        // 主串与模式串对其的第一个字符
        int i = 0;
        while (i <= n - m) {
            // 模式串从后往前匹配
            for (int j = m - 1; j >= 0; j--) {
                if (a[i + j] != b[j]) {
                    break;
                }
                if (j < 0) {
                    // 匹配成功，返回主串与模式串与模式串第一个匹配的字符位置
                    return i;
                }
                // 将模式串往后移动，j-bc[a[i+j]]
                int move = (int) a[i + j];
                i = i + (j - bc[move]);
            }
        }
        return -1;
    }

}
